package library;

public class UnionFind {
	
	class Node{
		int rank;
		Node parent;
		
		public Node(){
			parent = this;
			rank = 0;
		}
	}
	
	void Union(Node n, Node m){
		 Node nRoot = Find(n);
		 Node mRoot = Find(m);
		 
	     if (nRoot == mRoot)
	         return;

	     // x and y are not already in same set. Merge them.
	     if (nRoot.rank < mRoot.rank)
	    	 nRoot.parent = mRoot;
	     else if (nRoot.rank > mRoot.rank)
	    	 mRoot.parent = nRoot;
	     else{
	    	 mRoot.parent = nRoot;
	         nRoot.rank = nRoot.rank + 1;
	     }
	}

	//Get root node
	Node Find(Node n){
		if(n.parent==n)
			return n;
		else{
			n.parent = Find(n.parent);
			return n.parent;
		}
	}
}
